Multi-user virtual environment systems incorporate computer graphics, sound, and optionally networking to simulate the experience of real-time interaction between multiple users who are represented by avatars in a shared three-dimensional (3D) virtual world. A multi-user system allows a user to “explore” information and “interact” with other users in the context of a virtual environment by rendering images and sounds of the environment in real-time while the user's avatar moves through the 3D environment interactively. Example applications for multi-user systems include collaborative design, distributed training, teleconferencing, and multi-player games.
A difficult challenge for implementing a multi-user system is rendering realistic sounds that are spatialized according to the virtual environment in real-time for each user. Sound waves originating at a source location travel through the environment along a multitude of reverberation paths, representing different sequences of acoustic reflections, transmissions, and diffractions.
FIG. 1 illustrates, in 2D, just some of the possible acoustic reverberation paths between a sound source S and a receiver R in a simple two-room environment. The different arrival times and amplitudes of sound waves traveling along possible reverberation paths provide important auditory cues for localization of objects, separation of simultaneous speakers (i.e., the “cocktail party effect”), and sense of presence in the virtual environment. Because sound generally travels between a source and a receiver along a large number of paths, via reflection, transmission, and diffraction, realistic accurate acoustic simulation, particularly when sound sources and receivers are moving, is extremely computationally expensive.
One known acoustic modeling approach, known as beam tracing, classifies reverberation paths originating from a source position by recursively tracing pyramidal beams (i.e., a set of rays) through space. More specifically, a set of pyramidal beams is constructed that completely covers the two-dimensional (2D) space of directions from the source. For each beam, polygons that represent surfaces in the virtual space (e.g., walls, windows, doors, etc.) are considered for intersection in front-to-back order from the source. As intersecting polygons are detected, the original beam is “clipped” to remove the shadow region created by the intersecting polygon, a transmission beam is constructed matching the shadow region, and a specular reflection beam is constructed by mirroring the transmission beam over the intersecting polygon's plane.
FIGS. 2 and 3 illustrate, in 2D, these general principles of a beam tracing technique. In FIG. 2, a specular reflection beam Ra is constructed by mirroring a transmission beam over surface a, using S′ as a virtual beam source. The transmission beam Ta is constructed to match the shadow region created by surface a. Since each beam represents the region of space for which a corresponding virtual source (at the apex of the beam) is visible, high order virtual sources must be considered only for reflections off polygons intersecting the beam. For instance, referring to FIG. 3, consider the virtual source Sa which results from the specular reflection of the beam originating from S over polygon a. The corresponding reflection beam, Ra, intersects exactly the set of polygons (c and d) for which second-order reflections are possible after specular reflection off polygon a. Other polygons (b, e, f, and g) need not be considered for second-order reflections after a, thus significantly pruning the recursion tree of virtual sources.
A significant disadvantage of conventional beam tracing techniques, however, is that the geometric operations which are required to trace beams through the virtual environment (i.e., computing intersections, clipping, and mirroring) are computationally expensive, particularly when the source and/or the receiver are/is moving. Because each beam may be reflected and/or obstructed by several surfaces, particularly in complex environments, it is difficult to perform the necessary geometric operations on beams efficiently as they are recursively traced through the spatial environment. Generally, current acoustic modeling techniques are “off-line” systems which compute reverberation paths for a small set of pre-specified source and receiver locations, and allow interactive evaluation only for pre-computed results. Unfortunately, it is usually not possible to store pre-computed impulse responses or reverberation paths over all possible avatar locations for use by a multi-user system because the storage requirements of this approach would be prohibitive for all cases except very simple environments or very coarse samplings.
Significant advances have been made in multi-user systems supporting visual interactions between users in a shared 3D virtual environment. The most common examples of such advancements are multi-player games which display images in real-time with complex global illumination and textures to produce visually compelling and immersive experiences. On the other hand, there has been little progress in realistic acoustic modeling in such virtual environments.